package codingforgreat.class15;

public class Class03_LC_123 {
    //必须两笔
    public int maxProfit(int[] prices) {
        return maxProfit1(2, prices);
    }
    public static int allTrans(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            ans += Math.max(prices[i] - prices[i - 1], 0);
        }
        return ans;
    }
    public int maxProfit1(int k, int[] prices) {
/*
        dp[i][j] j = 0 -> 开始不交易为0
        情况第i次交不交易
        dp[8][3] = Math.max(dp[7][3], dp[7][2] + p[8] - p[7],
         dp[6][2] + p[8] - p[6] ... dp[0][2] + p[8] -p[0]  )

         枚举优化
        dp[5][2] =  Math.max(dp[4][2], dp[4][1] + p[5] - p[4],dp[3][1] + p[5] - p[3] ... dp[0][1] + p[5] -p[0])
        dp[6][2] = Math.max(dp[5][2], dp[5][1] + p[6] - p[5],dp[4][1] + p[6] - p[4] ... dp[0][1] + p[6] -p[0])

        dp[i][j] = Math.max( dp[i][j - 1], Math.max( dp[i][j-1]-p[i] ) + p[i])
        dp[5][2] 无法帮助dp[5][3] 竖着填
        */

        if (prices == null || prices.length == 0 || k < 1) {
            return 0;
        }
        int N = prices.length;
        if (k >= N / 2) {
            return allTrans(prices);
        }
        int[][] dp = new int[prices.length][k + 1];
        for (int j = 1; j <= k ; j++) {
            int p1 = dp[1][j - 1];
            int best = Math.max(dp[1][j - 1] - prices[1], dp[0][j - 1] - prices[0]);
            dp[1][j] = Math.max(p1, best + prices[1]);
            for (int i = 2; i < prices.length ; i++) {
                p1 = dp[i - 1][j];
                int newp = dp[i][j - 1] - prices[i];
                best = Math.max(best, newp);
                dp[i][j] = Math.max(p1, best + prices[i]);
            }
        }
        return dp[prices.length - 1][k];
    }
}
